package offerv1;

import leetcodev1.链表.Solution;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Offer49 {
    public int nthUglyNumber1(int n) {
        int num = 1;
        while (n > 0) {
            if (isUglyNumber(num)) {
                n--;
            }
            num++;
        }

        return num - 1;
    }

    private boolean isUglyNumber(int num) {
        while (num != 1) {
            if (num % 5 == 0) {
                num /= 5;
                continue;
            }

            if (num % 3 == 0) {
                num /= 3;
                continue;
            }

            if (num % 2 == 0) {
                num /= 2;
                continue;
            }

            return false;
        }

        return true;
    }


    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        //进行n轮
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();//每次取最小元素
            ugly = (int) curr;
            //再放三个元素进去
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }

}
